package com.sali.排序.raw;

/**
 * Step1: 选择一个基准值（Pivot）。
 * Step2: 将数组分为两部分：左边元素 ≤ 基准值，右边元素 ≥ 基准值（分区操作）。
 * Step3: 递归对左右子数组重复上述步骤，直到子数组长度为 1（自然有序）。
 */
public class raw5_快速排序 {

    public static void main(String[] args) {
        int[] arr = {3, 5, 1, 6, 2, 7, 4};
        quickSort(arr, 0, arr.length - 1);
        for (int element : arr) {
            System.out.print(element + " ");
        }
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = getPivot(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }

    private static int getPivot(int[] arr, int left, int right) {
        int pivotVal = arr[right];
        int index = left - 1;
        for (int i = left; i < right; i++) {
            if (arr[i] < pivotVal) {
                index += 1;
                swap(arr, index, i);
            }
        }
        swap(arr, index + 1, right);
        return index + 1;
    }

    private static void swap(int[] arr, int p1, int p2) {
        int tmp = arr[p1];
        arr[p1] = arr[p2];
        arr[p2] = tmp;
    }

}
